/**
 * 剑指 Offer 14- II. 剪绳子 II
 * https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/
 */

const mod = 1e9 + 7;

/**
 * @param {number} n
 * @return {number}
 */
function cuttingRope(n) {
  if (n === 2) {
    return 1;
  }
  if (n === 3) {
    return 2;
  }
  let threeCount = Math.floor(n / 3);
  let rem = 1;
  if (n % 3 === 1) {
    rem = 4;
    threeCount -= 1;
  } else if (n % 3 === 2) {
    rem = 2;
  }
  for (let i = 0; i < threeCount; i += 1) {
    rem = (rem * 3) % mod;
  }
  return rem;
}

console.log(cuttingRope(10) === 36);
console.log(cuttingRope(1000) === 620946522);
